//
// Created by Snow on 2023/5/15.
//
//折半插入算法
#include"seqlist.cpp"
void BinInsertSort(RecType R[],int n)
{
    int i,j,low,high,mid;
    RecType temp;
    for(i=1;i<n;i++)
    {
        if(R[i].key<R[i-1].key)//反序时
        {
            temp=R[i];//将R[i]保存到temp中
            low=0;
            high=i-1;
            while(low<=high)//在R[low..high]中查找插入的位置
            {
                mid=(low+high)/2;//取中间位置
                if(temp.key<R[mid].key)//插入点在左半区
                    high=mid-1;
                else//插入点在右半区
                    low=mid+1;
            }//找位置high
            for(j=i-1;j>=high+1;j--)//集中进行元素后移
                R[j+1]=R[j];
            R[high+1]=temp;//插入temp
        }
    }
}
int main()
{
    int n=10;
    RecType R[MAXL];
    KeyType a[]={9,8,7,6,5,4,3,2,1,0};
    CreateList(R,a,n);
    DispList(R,n);
    BinInsertSort(R,n);
    DispList(R,n);
    return 1;
}
